package DoExercise.HSP_ZCY.A015_暴力递归;

/**
 * 给定一个整型数组arr，代表数值不同的纸牌排成一条线，
 * 玩家A和玩家B依次拿走每张纸牌，
 * 规定玩家A先拿，玩家B后拿，
 * 但是每个玩家每次只能拿走最左或最右的纸牌，
 * 玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
 * <p>
 * 零和博弈
 * <p>
 * 范围上的尝试模型
 */
public class Code08_拿牌问题
{
    public static void main(String[] args)
    {
        int[] arr = {20, 19, 120, 100};
        System.out.println(win1(arr));
    }
    
    public static int win1(int[] arr)
    {
        if (arr == null || arr.length == 0)
        {
            return 0;
        }
        //A先手拿 和 B后手拿 的最大分数
        return Math.max(first(arr, 0, arr.length - 1), second(arr, 0, arr.length - 1));
    }
    
    /**
     * 先手函数
     * 先手拿获取的最大分数
     *
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int first(int[] arr, int L, int R)
    {
        if (L == R)//只有一张牌
        {
            return arr[L];
        }
        return Math.max(arr[L] + second(arr, L + 1, R), arr[R] + second(arr, L, R - 1));//你自己会按照自己拿到最大的分数拿牌
    }
    
    /**
     * 后手函数
     * 后手拿获取的最大分数
     *
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int second(int[] arr, int L, int R)
    {
        if (L == R)//没牌了
        {
            return 0;
        }
        //当你选择时，后手，一定要选择先手最少的情况，这样你才能拿的最多
        return Math.min(first(arr, L + 1, R), first(arr, L, R - 1));
    }
}
